//设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 
//
// 实现 MinStack 类: 
//
// 
// MinStack() 初始化堆栈对象。 
// void push(int val) 将元素val推入堆栈。 
// void pop() 删除堆栈顶部的元素。 
// int top() 获取堆栈顶部的元素。 
// int getMin() 获取堆栈中的最小元素。 
// 
//
// 
//
// 示例 1: 
//
// 
//输入：
//["MinStack","push","push","push","getMin","pop","top","getMin"]
//[[],[-2],[0],[-3],[],[],[],[]]
//
//输出：
//[null,null,null,null,-3,null,0,-2]
//
//解释：
//MinStack minStack = new MinStack();
//minStack.push(-2);
//minStack.push(0);
//minStack.push(-3);
//minStack.getMin();   --> 返回 -3.
//minStack.pop();
//minStack.top();      --> 返回 0.
//minStack.getMin();   --> 返回 -2.
// 
//
// 
//
// 提示： 
//
// 
// -2³¹ <= val <= 2³¹ - 1 
// pop、top 和 getMin 操作总是在 非空栈 上调用 
// push, pop, top, and getMin最多被调用 3 * 10⁴ 次 
// 
// Related Topics 栈 设计 👍 1215 👎 0

package leetcode.editor.cn;

import java.util.*;

public class _155_MinStack {
    public static void main(String[] args) {
        MinStack minStack = new _155_MinStack().new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());
    }

    class MinStack {
        private class Node {
            int val;
            int min;
            Node next;

            private Node(int val, int min) {
                this.val = val;
                this.min = min;
            }

            private Node(int val, int min, Node next) {
                this.val = val;
                this.min = min;
                this.next = next;
            }
        }

        private Node head;

        public MinStack() {
        }

        public void push(int val) {
            if (head == null) {
                head = new Node(val, val);
            } else {
                head = new Node(val, Math.min(head.min, val), head);
            }
        }

        public void pop() {
            head = head.next;
        }

        public int top() {
            return head.val;
        }

        public int getMin() {
            return head.min;
        }

    }

    class MinStack2 {
        private class Node{
            private int val;
            private int min;

            private Node(int val, int min) {
                this.val = val;
                this.min = min;
            }
        }

        Deque<Node> stack;



        public MinStack2() {
            stack = new ArrayDeque<>();
        }

        public void push(int val) {
            if (stack.isEmpty()) {
                stack.addLast(new Node(val, val));
            } else {
                stack.addLast(new Node(val, Math.min(stack.peekLast().min, val)));
            }
        }

        public void pop() {
            stack.removeLast();
        }

        public int top() {
            return stack.peekLast().val;
        }

        public int getMin() {
            return stack.peekLast().min;
        }
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class MinStack1 {
        Deque<Integer> stack;
        Deque<Integer> minStack;


        public MinStack1() {
            stack = new ArrayDeque<>();
            minStack = new ArrayDeque<>();
            minStack.addLast(Integer.MAX_VALUE);
        }

        public void push(int val) {
            stack.addLast(val);
            minStack.addLast(Math.min(val, minStack.peekLast()));
        }

        public void pop() {
            stack.removeLast();
            minStack.removeLast();
        }

        public int top() {
            return stack.peekLast();
        }

        public int getMin() {
            return minStack.peekLast();
        }
    }

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */
//leetcode submit region end(Prohibit modification and deletion)

}